//
//  main.c
//  希尔sort
//
//  Created by Song on 2018/4/2.
//  Copyright © 2018年 Song. All rights reserved.
//

//  (nlog2n) （n^1.3）

#include <stdio.h>

int main(int argc, const char * argv[]) {
    
    int r[10] = {59,20,17,36,98,14,23,83,13,28};
    int n = 10;
    int d; // 增量
    int i,j,temp;
    
//    do{ // 大话数据结构
//        //
//        increment = increment / 3 + 1; //  = 9 / 3 + 1 = 4
//        
//        for (i = increment + 1; i <= length; i++) { // i = 5 --> 9
//            if ( r[i] > r[i - increment] ) {
//                
//                r[0] = r[i]; // 哨兵
//                
//                for (j = i-increment; j>0 && r[0]<r[j]; j-=increment) {
//                    r[j+increment] = r[j]; // 记录后移
//                }
//                
//                r[j+increment] = r[0];
//            }
//        }
//        
//    }while (increment > 1);
    
    for (d = n/2; d >=1; d = d/2) {
        for (i = d; i < n; i++) {
            temp = r[i]; // temp 暂存 (存的是后面的)
            for (j = i-d; j>=0 && temp<r[j]; j = j-d) { // 后面的temp<前面的，就移位
                r[j+d] = r[j];
            }
            r[j+d] = temp;
        }
    }
    
    for (int a = 0; a<10; a++) {
        printf("%d ",r[a]);
    }
    
    printf("\n");
    return 0;
}
